
#include <iostream>
#include <cstdlib>
#include "bsp-generator.h"


Room::Room(int xx1, int xx2, int yy1, int yy2)
{
	x1 = xx1;
	x2 = xx2;
	y1 = yy1;
	y2 = yy2;
//	std::cout << x1 << " " << x2 << " " << y1 << " " << y2 << std::endl;
}

Tree_Node::Tree_Node(Tree_Node *myparent, int x1, int x2, int y1, int y2)
{
	room = new Room(x1, x2, y1, y2);
	left = NULL;
	right = NULL;
	parent = myparent;
	hasldoor = false;
	hasrdoor = false;
	hastdoor = false;
	hasbdoor = false;
}

Tree_Node::~Tree_Node()
{
	if (left != NULL)
		delete left;
	if (right != NULL)
		delete right;
	delete room;
}

bool Tree_Node::isLeaf()
{
	if ((left == NULL) && (right == NULL))
		return true;
	else
		return false;
}

Tree::Tree(int width, int height)
{
	HEAD = new Tree_Node(NULL, 0, width-1, 0, height-1);
}

Tree::~Tree()
{
	if (HEAD != NULL)
		delete HEAD;
}

Tree_Node *Tree::head()
{
	return HEAD;
}

void Tree::printTree()
{
	printTreeHelper(HEAD);
}

void Tree::printTreeHelper(Tree_Node *t)
{
	if (t->left != NULL)
		printTreeHelper(t->left);
	if (t->right != NULL)
		printTreeHelper(t->right);
	std::cout << t->room->x1 << " " << t->room->x2 << " " << t->room->y1 << " " << t->room->y2 << std::endl;
	return;
}

BSP_Generator::BSP_Generator(Mersenne_Twister *r, int width, int height, bool hasdownstairs, bool hasupstairs)
{		
	RNG = r;
	WIDTH = width;
	HEIGHT = height;
	HASDOWNSTAIRS = hasdownstairs;
	HASUPSTAIRS = hasupstairs;
	BSP = new Tree(WIDTH, HEIGHT);
	MAP.resize(WIDTH*HEIGHT);
	generateDungeon();
//	BSP->printTree();
}

BSP_Generator::~BSP_Generator()
{
	if (BSP != NULL)
		delete BSP;
}

void BSP_Generator::generateDungeon()
{
	for (int i=0; i<HEIGHT; i++)
	{
		for (int j=0; j<WIDTH; j++)
		{
			MAP[i*WIDTH+j] = '.';		// Initialize the map to the default floor tile.
//			std::cout << MAP[i*WIDTH+j];
		}
//		std::cout << std::endl;
	}
	
	generateHelper(BSP->head());
	generateWalls();
	generateDoors();
	generateStairs();
}

void BSP_Generator::generateHelper(Tree_Node *tn)
{
	int x = tn->room->x2 - tn->room->x1;
	int y = tn->room->y2 - tn->room->y1;
	int d;
	int r = RNG->rand();
	bool finished = false;
	
	
	if ((x <= 15) && (y <= 10))	// Do not generate rooms or levels less than 25 square units.
	{
		tn->left = NULL;
		tn->right = NULL;
//		std::cout << "Creating Room: " << tn->isLeaf() << tn->room->x1 << " " << tn->room->x2 << "  " << tn->room->y1 << " " << tn->room->y2  << std::endl;
		return;
	}
	
	if ((x <= 15) && (y > 10))
		tn->vertical = false;
	else if ((x > 15) && (y < 10))
		tn->vertical = true;
	else if ((r%2) == 0)
		tn->vertical = true;
	else
		tn->vertical = false;
		
	if (tn->vertical == true)
	{
		while(finished == false)
		{
//			d = ((RNG->rand() % (x - 7)) + 6) + tn->room->x1;
			d = (RNG->rand() % x) + tn->room->x1;
//			std::cout << d << std::endl;
			if ((d > (tn->room->x1 + 4)) && (d < (tn->room->x2 - 4)))	// if d is within the requested range
				finished = true;
		}	
//		std::cout << "vertical cut " << d << std::endl;
		tn->left = new Tree_Node(tn, tn->room->x1, d, tn->room->y1, tn->room->y2);
		tn->right = new Tree_Node(tn, d, tn->room->x2, tn->room->y1, tn->room->y2);
	}
	else
	{
		while(!finished)
		{
//			d = ((RNG->rand() % (x - 7)) + 6) + tn->room->x1;
			d = (RNG->rand() % y) + tn->room->y1;
//			std::cout << d << std::endl;
			if ((d > (tn->room->y1 + 4)) && (d < (tn->room->y2 - 4)))	// if d is within the requested range
				finished = true;
		}
//		std::cout << "horizontal cut " << d << std::endl;
		tn->left = new Tree_Node(tn, tn->room->x1, tn->room->x2, tn->room->y1, d);
		tn->right = new Tree_Node(tn, tn->room->x1, tn->room->x2, d, tn->room->y2);
	}
	
//	std::cout << "Creating Room: " << tn->isLeaf() << " " << tn->room->x1 << " " << tn->room->x2 << "  " << tn->room->y1 << " " << tn->room->y2  << std::endl;

	generateHelper(tn->left);
	generateHelper(tn->right);
}

// This function creates walls around each room.
void BSP_Generator::generateWalls()
{
	generateWallHelper(BSP->head());
}

void BSP_Generator::generateWallHelper(Tree_Node *t)
{
	if (t->isLeaf())		// Only generate walls around the rooms in the leaf nodes of the tree to prevent overlap.
	{
		Room *r = t->room;
		for (int i=r->x1; i<=r->x2; i++)
		{
			MAP[(r->y1)*WIDTH+i] = '#';
			MAP[(r->y2)*WIDTH+i] = '#';
		}
		for (int j=r->y1; j<=r->y2; j++)
		{
			MAP[j*WIDTH+r->x1] = '#';
			MAP[j*WIDTH+r->x2] = '#';
		}
	}
	else
	{
		generateWallHelper(t->left);
		generateWallHelper(t->right);
	}
	return;
}

void BSP_Generator::printDungeon()
{
	std::cout << "Printing Map:" << std::endl;
	for (int i=0; i<HEIGHT; i++)
	{
		for (int j=0; j<WIDTH; j++)
		{
			std::cout << MAP[i*WIDTH+j];
		}
		std::cout << std::endl;
	}
}

void BSP_Generator::printRooms()
{
	std::cout << "Printing Rooms:" << std::endl;
	printHelper(BSP->head());
}

void BSP_Generator::printHelper(Tree_Node *t)
{
	if (t->isLeaf() == true)
		std::cout << t->room->x1 << " " << t->room->x2 << " " << t->room->y1 << " " << t->room->y2 << std::endl;
	else
	{
		printHelper(t->left);
		printHelper(t->right);
	}
}

char BSP_Generator::isAt(int x, int y)
{
	return MAP[y*WIDTH+x];
}

void BSP_Generator::generateDoors()
{
	generateDoorHelper(BSP->head());
}

void BSP_Generator::generateDoorHelper(Tree_Node *t)
{
	if (t->isLeaf() == true)
	{
//		std::cout << "Generating door for " << t->room->x1 << " " << t->room->x2 << " " << t->room->y1 << " " << t->room->y2 << std::endl;
		bool hasdoorone = false, hasdoortwo = false;
		int a = t->room->x2 - t->room->x1 - 1;			// Subtracting one ensures that no door is created in the
		int b = t->room->y2 - t->room->y1 - 1;			// corners of each room.
		int pos;
		
									// First, create doors in vertical walls.
		for (int i=1; i<=b; i++)				// Check to see if a door has already been created in this wall section.
		{
			if (MAP[(t->room->y1 + i) * WIDTH + t->room->x1] == '+')
				hasdoorone = true;
			if (MAP[(t->room->y1 + i) * WIDTH + t->room->x2] == '+')
				hasdoortwo = true;
/*			
			if (hasdoorone==true)
				std::cout << "Wall[" << t->room->y1 << ".." << t->room->y2 << "][" << t->room->x1 << "] already has a wall!" << std::endl;
			else
				std::cout << "Generating door for Wall[" << t->room->y1 << ".." << t->room->y2 << "][" << t->room->x1 << "]!" << std::endl;
			if (hasdoortwo==true)
				std::cout << "Wall[" << t->room->y1 << ".." << t->room->y2 << "][" << t->room->x2 << "] already has a wall!" << std::endl;
			else
				std::cout << "Generating door for Wall[" << t->room->y1 << ".." << t->room->y2 << "][" << t->room->x2 << "]!" << std::endl;
 */
		}
		
		if ((!hasdoorone) && (t->room->x1 != 0))		// Do not make a door in the left or right border of the map.
		{
			pos = (RNG->rand() % b) + 1;
			MAP[(t->room->y1 + pos) * WIDTH + t->room->x1] = '+';
//			std::cout << (t->room->y1 + pos) << " " << t->room->x1 << " " << MAP[(t->room->y1 + pos) * WIDTH + t->room->x2] << std::endl;
		}
		
		if ((!hasdoortwo) && (t->room->x2 != (WIDTH-1)))	// Do not make a door in the left or right border of the map.
		{
			pos = (RNG->rand() % b) + 1;
			MAP[(t->room->y1 + pos) * WIDTH + t->room->x2] = '+';
//			std::cout << (t->room->y1 + pos) << " " << t->room->x2 << " " << MAP[(t->room->y1 + pos) * WIDTH + t->room->x2] << std::endl;
		}		
		
		hasdoorone = false;
		hasdoortwo = false;
		
									// Next, create doors in horizontal walls.
		for (int j=1; j<=a; j++)				// Check to see if a door has already been created in this wall section.
		{
			if (MAP[t->room->y1 * WIDTH + (t->room->x1 + j)] == '+')
				hasdoorone = true;
			if (MAP[t->room->y2 * WIDTH + (t->room->x1 + j)] == '+')
				hasdoortwo = true;
/*			
			if (hasdoorone==true)
				std::cout << "Wall[" << t->room->y1 << "][" << t->room->x1 << ".." << t->room->x2 << "] already has a wall!" << std::endl;
			else
				std::cout << "Generating door for Wall[" << t->room->y1 << "][" << t->room->x1 << ".." << t->room->x2 << "]!" << std::endl;
 				
			if (hasdoortwo==true)
				std::cout << "Wall[" << t->room->y2 << "][" << t->room->x1 << ".." << t->room->x2 << "] already has a wall!" << std::endl;
			else
				std::cout << "Generating door for Wall[" << t->room->y2 << "][" << t->room->x1 << ".." << t->room->x2 << "]!" << std::endl;
 */				
		}
		
		if ((!hasdoorone) && (t->room->y1 != 0))		// Do not make a door in the top or bottom border of the map.
		{
			pos = (RNG->rand() % a) + 1;
			MAP[t->room->y1 * WIDTH + (t->room->x1 + pos)] = '+';
//			std::cout << t->room->y1 << " " << t->room->x1 + pos << " " << MAP[t->room->y1 * WIDTH + (t->room->x1 + pos)] << std::endl;
		}
		if ((!hasdoortwo) && (t->room->y2 != (HEIGHT-1)))	// Do not make a door in the top or bottom border of the map.
		{
			pos = (RNG->rand() % a) + 1;
			MAP[t->room->y2 * WIDTH + (t->room->x1 + pos)] = '+';
//			std::cout << t->room->y2 << " " << t->room->x1 + pos << " " << MAP[t->room->y2 * WIDTH + (t->room->x1 + pos)] << std::endl;
		}	
	}
	else
	{
		generateDoorHelper(t->left);
		generateDoorHelper(t->right);
	}
}

void BSP_Generator::generateStairs()
{
	bool found = false;
	char c;
	int x, y;
	if (HASDOWNSTAIRS)				// Place Down stairs.
	{
		while (!found)
		{
			x = RNG->rand() % (WIDTH-1);
			y = RNG->rand() % (HEIGHT-1);
			if ((MAP[y*WIDTH+x] != '#') || (MAP[y*WIDTH+x] != '+') || (MAP[y*WIDTH+x] != '<'))
			{
				MAP[y*WIDTH + x] = '>';
				found = true;
			}
		}
	}
	found = false;
	
	if (HASUPSTAIRS)				// Place Up stairs.
	{
		while (!found)
		{
			x = RNG->rand() % (WIDTH-1);
			y = RNG->rand() % (HEIGHT-1);
			if ((MAP[y*WIDTH+x] != '#') || (MAP[y*WIDTH+x] != '+') || (MAP[y*WIDTH+x] != '>'))
			{
				MAP[y*WIDTH + x] = '<';
				found = true;
			}
		}
	}
}

